/*
 * @lc app=leetcode.cn id=56 lang=typescript
 *
 * [56] 合并区间
 */

// @lc code=start
function merge(intervals: number[][]): number[][] {
  const size = intervals.length;
  if (intervals.length === 0) return [];

  // 保存区间左右边界状态
  const marks: number[][] = [];
  // 左边界，状态1。
  // 右边界，状态-1。
  for (let [l, r] of intervals) {
    marks.push([l, 1]);
    marks.push([r, -1]);
  }
  // 按照左边界升序
  // 如果左边界相同，按照状态降序
  marks.sort((a, b) => {
    if (a[0] - b[0]) {
      return a[0] - b[0];
    } else {
      return b[1] - a[1];
    }
  });

  const result: number[][] = [];
  let left = -1;
  let count = 0;
  for (let [idx, mark] of marks) {
    if (left === -1) left = idx;
    // 累计计算状态值
    count += mark;
    // 如果为0，就找到一个合并区间，更新答案
    if (count === 0) {
      result.push([left, idx]);
      left = -1;
    }
  }

  return result;
}
// @lc code=end
